package solutions.leetcode.normal;

import solutions.lib.BaseSolution;
import solutions.lib.TreeNode;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/">1123. 最深叶节点的最近公共祖先</a>
 */
public class Solution1123 extends BaseSolution {

    static class Model {
        TreeNode node;
        int height;

        public Model(TreeNode node, int height) {
            this.node = node;
            this.height = height;
        }
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        Model model = check(root);
        return model.node;
    }

    private Model check(TreeNode root) {
        if (root == null) {
            return null;
        }
        Model left = check(root.left);
        Model right = check(root.right);
        int hl = left == null ? -1 : left.height;
        int hr = right == null ? -1 : right.height;
        if (hl == hr) {
            return new Model(root, hl + 1);
        } else if (hl > hr) {
            left.height++;
            return left;
        } else {
            right.height++;
            return right;
        }
    }

    public static void main(String[] args) {
        Solution1123 solution = new Solution1123();
    }
}